Steven_Meng's Blog

传送门
这道题比较有意思
考虑记录一个$tag$表示员工工资应该加上多少。
加工资的操作不会导致员工离开
但是扣工资的操作会导致工资所有小于$min-tag$的员工离开

怎么删除所有小于$min-tag$的值呢？
yy一下，发现FHQ Treap中$num$左子树的值都小于num
于是每次删除所有小于$min-tag$的值时，删除其左子树即可

// luogu-judger-enable-o2
#include <bits/stdc++.h>
#define MAXN 500005
using namespace std;
inline int read() {
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9') {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9') {
        x=(x*10)+(ch-'0');
        ch=getchar();
    }
    return x*f;
}
namespace FHQ_Treap{
	struct node{
		int l,r;
		int val;//每个点的权值 
		int pri;//优先级（随机生成）
		int sz; 
	}tree[MAXN];
	int tot;
	#define lc(i) tree[i].l
	#define rc(i) tree[i].r
	inline void Update(int x){
		tree[x].sz=tree[lc(x)].sz+tree[rc(x)].sz+1;
	}
	inline int New(int v){
		tree[++tot].val=v;
		tree[tot].pri=rand();
		tree[tot].sz=1;
		return tot;
	}
	int Merge(int x,int y){
		if (!x||!y) return x+y;
		if (tree[x].pri<tree[y].pri){
			rc(x)=Merge(rc(x),y),Update(x);
			return x;
		}
		else {
			lc(y)=Merge(x,lc(y)),Update(y);
			return y;
		}
	}
	void Split(int i,int k,int &x,int &y){
		if (!i){//叶节点
			x=y=0;
		}
		else {
			if (tree[i].val<=k){x=i,Split(rc(i),k,rc(i),y);}
			else{y=i,Split(lc(i),k,x,lc(i));}
			Update(i);
		}
	}
	int kth(int i,int k){//排名为k
		while (true){
			if (k<=tree[lc(i)].sz){
				i=lc(i);
			}
			else if (k==tree[lc(i)].sz+1){
				return i;
			}
			else{
				k-=tree[lc(i)].sz+1;
				i=rc(i);
			}
		}
	}
    //以上为FHQ Treap
    int root,x,y,z;
    void Init(){
        tot=0;
        memset(tree,0,sizeof(tree));
        root=0;
        srand(19260817);
    }
    inline void Add(int num){
		Split(root,num,x,y);
		root=Merge(Merge(x,New(num)),y);
    }
    inline void Del(int num){
		Split(root,num,x,z);
		Split(x,num-1,x,y);
		y=Merge(lc(y),rc(y));
		root=Merge(Merge(x,y),z);
    }
	#define Get_K(rt,rk) tree[kth(rt,rk)].val
    inline int Kth(int k){//获得数组中第k大
        if (tree[root].sz<k) return -1;
		return Get_K(root,tree[root].sz-k+1);
    }
    inline int Pre(int num){
        Split(root,num-1,x,y);
		int temp=Get_K(x,tree[x].sz);
		root=Merge(x,y);
        return temp;
    }
    inline int Delete_Pre(int num){
        //删除全部小于num的数，直接删除左子树
        Split(root,num-1,x,y);//x:左边
        root=y;
        return tree[x].sz;
    }
};
using namespace FHQ_Treap;
#define INF 0x3f3f3f3f
inline char gc(){
    char ch=getchar();
    while (ch!='I'&&ch!='A'&&ch!='S'&&ch!='F') ch=getchar();
    return ch;
}
int main(){
    Init();
    // Add(INF),Add(-INF);
    int n=read(),Min=read();
    int tag=0;//每个人的工资加上多少，类似于lazytag
    int sum=0;
    while (n--){
        char opr=gc();
        int num=read();
        if (opr=='I'){
            if (num<Min){continue;}//员工直接离开
            Add(num-tag);
        }
        else if (opr=='A'){
            tag+=num;//加工资的操作不会导致员工离开
        }
        else if (opr=='S'){
            tag-=num;
            sum+=Delete_Pre(Min-tag);
        }
        else if (opr=='F'){
            int ans=Kth(num);
            if (ans==-1) printf("-1\n");
            else printf("%d\n",ans+tag);
        }
    }
    printf("%d\n",sum);
}